package com.zx._12_算法.数据结构.bitmap;

import java.util.Arrays;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: 数字生成短链  大数据排序
 * @Description: 有多达10亿无序整数，已知最大值为15亿，请对这个10亿个数进行排序。
 *         传统排序算法都不可能解决这个排序问题，即便内存允许，其计算时间也是漫长的，如果使用BitMap就极为简单。
 *         BitMap存储最大值为15亿的集合，只需要180M的空间，空间使用完全可以接受，至于速度，存储和比较过程中的位运算速度都非常快，第一次遍历，
 *         将10亿个数都放入到BitMap中，第二次，从0到15亿进行遍历，如果在BitMap，则输出该数值，这样经过两次遍历，就可以将如此多的数据排序。
 *         为了演示方便，只用一个很小的数组，[0, 6, 88, 7, 73, 34, 10, 99, 22]，已知数组最大值是99，利用BitMap排序的算法如下
 * @author: zhangxue
 * @date: 2019年8月4日下午7:22:52
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class Demo1 {

    public static void main(String[] args) {
        int[] datas = {0, 6, 88, 7, 73, 34, 10, 99, 22};
        BitMap bitMap = new BitmapImpl1();
        for (int i = 0; i < datas.length; i++) {
            bitMap.addMember(datas[i]);
        }

        int[] data2 = new int[datas.length];
        int index = 0;
        for (int i = 0; i < 100; i++) {
            boolean exist = bitMap.isExist(i);
            if (exist) {
                data2[index] = i;
                index++;
            }
        }
        //[ 0, 6, 7, 10, 22, 34, 73, 88, 99 ]
        System.out.println(Arrays.toString(data2));
    }
}
